package com.ljy.my_study.leetcode.有效三角形的个数;

import java.util.Arrays;

public class TestMain {

//    给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
//
//    示例 1:
//
//    输入: [2,2,3,4]
//    输出: 3
//    解释:
//    有效的组合是:
//            2,3,4 (使用第一个 2)
//            2,3,4 (使用第二个 2)
//            2,2,3
//    注意:
//
//    数组长度不超过1000。
//    数组里整数的范围为 [0, 1000]。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/valid-triangle-number
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //排序+二分查找
    public static void main(String[] args) {
        System.out.println(new TestMain().triangleNumber(new int[]{1,2,3,3}));
    }

    public int triangleNumber(int[] nums) {
        if(nums==null||nums.length<=2){
            return 0;
        }
        int count=0;
        Arrays.sort(nums);
        int length=nums.length;
        for(int i=0;i<length-2;i++){
            if(nums[i]==0){
                continue;
            }
            for(int j=i+1;j<length-1;j++){
                int sum=nums[i]+nums[j];
                int index=findIndex(nums,j+1,length-1,sum);
                if(index-j>0){
                    count+=index-j;
                }
            }
        }
        return count;
    }

    private int findIndex(int[] nums,int left,int right,int num){
        if(num<nums[left]){
            return -1;
        }
        if(num>nums[right]){
            return right;
        }
        int minLeft=left;
        while(left<right){
            int mid=(left+right)/2;
            if(left==mid){
                if(nums[mid]<num){
                    return mid;
                }else{
                    return -1;
                }
            }
            if(num>nums[mid]){
                left=mid;
            }else if(num<nums[mid]){
                right=mid;
            }else{
                while(mid>=minLeft&&nums[mid]==num){
                    mid--;
                }
                return mid;
            }
        }
        return -1;
    }
}
